import random
from collections import defaultdict


def generate_one_round_order(team_count: int) -> list[list[int]]:
    """
    生成一个随机的队伍出场顺序列表
    :param team_count: 队伍总数
    :return: 随机顺序的队伍ID列表
    """
    if team_count <= 0:
        return []

    # 生成所有队伍并随机打乱
    all_teams = list(range(1, team_count + 1))
    random.shuffle(all_teams)

    # 分成每3队一组
    result = []
    for i in range(0, team_count, 3):
        round_teams = all_teams[i:i + 3]
        result.append(round_teams)

    # 处理剩余队伍
    if len(result) > 1:
        if len(result[-1]) == 1:
            # 余1：将最后一个队伍合并到前一组
            remain = result.pop()
            result[-1].append(remain[0])
        elif len(result[-1]) == 2:
            # 余2：将两个队伍分别合并到前两组
            remain = result.pop()
            result[-1].append(remain[0])
            if len(result) > 1:  # 确保有倒数第二组
                result[-2].append(remain[1])
            else:
                result[-1].append(remain[1])  # 如果只有一组，都放在这一组

    return result


def generate_new_round_order(team_count: int, previous_orders: list[list[list[int]]]) -> list[list[int]]:
    """
    基于历史分组生成新的分组，避免先前同轮的队伍再次同轮
    """
    if team_count <= 0:
        return []

    # 构建历史同轮关系
    history_together = build_history_together(previous_orders)

    all_teams = list(range(1, team_count + 1))
    random.shuffle(all_teams)

    # 先生成基础分组（优开3，劣开4，禁止2）
    base_groups = []
    for i in range(0, team_count, 3):
        if i + 3 <= team_count:
            base_groups.append(all_teams[i:i + 3])
        else:
            base_groups.append(all_teams[i:])

    # 处理剩余队伍
    result = []
    remaining_teams = []

    # 先处理完整的3队组
    for group in base_groups:
        if len(group) == 3:
            result.append(group)
        else:
            remaining_teams.extend(group)

    # 处理剩余队伍：分配到前面的3队组形成4队组
    while remaining_teams:
        if result and len(result[-1]) == 3:
            result[-1].append(remaining_teams.pop(0))
        else:
            # 如果没有3队组了，创建新的4队组
            if len(remaining_teams) >= 4:
                result.append(remaining_teams[:4])
                remaining_teams = remaining_teams[4:]
            else:
                # 剩余少于4个，分配到前面的组
                for team in remaining_teams:
                    for group in result:
                        if len(group) < 4:
                            group.append(team)
                            break
                break

    # 现在对结果进行优化，避免历史同轮
    optimized_result = avoid_history_conflicts(result, history_together, team_count)
    optimized_result.sort(key=len)
    return optimized_result


def build_history_together(previous_orders):
    """构建历史同轮关系"""
    history_together = defaultdict(set)
    for order_table in previous_orders:
        for round_teams in order_table:
            for i in range(len(round_teams)):
                for j in range(i + 1, len(round_teams)):
                    team1, team2 = round_teams[i], round_teams[j]
                    history_together[team1].add(team2)
                    history_together[team2].add(team1)
    return history_together


def avoid_history_conflicts(groups, history_together, team_count):
    """避免历史同轮冲突"""
    max_attempts = 100

    for attempt in range(max_attempts):
        # 打乱所有队伍
        all_teams = list(range(1, team_count + 1))
        random.shuffle(all_teams)

        # 按照你的格式生成分组
        base_groups = []
        for i in range(0, team_count, 3):
            if i + 3 <= team_count:
                base_groups.append(all_teams[i:i + 3])
            else:
                base_groups.append(all_teams[i:])

        result = []
        remaining_teams = []

        for group in base_groups:
            if len(group) == 3:
                result.append(group)
            else:
                remaining_teams.extend(group)

        while remaining_teams:
            if result and len(result[-1]) == 3:
                result[-1].append(remaining_teams.pop(0))
            else:
                if len(remaining_teams) >= 4:
                    result.append(remaining_teams[:4])
                    remaining_teams = remaining_teams[4:]
                else:
                    for team in remaining_teams:
                        for group in result:
                            if len(group) < 4:
                                group.append(team)
                                break
                    break

        # 检查是否满足避免历史同轮的条件
        if is_valid_grouping(result, history_together):
            return result

    # 如果找不到完全无冲突的，返回冲突最少的
    return groups


def is_valid_grouping(groups, history_together):
    """检查分组是否满足避免历史同轮的条件"""
    for group in groups:
        for i in range(len(group)):
            for j in range(i + 1, len(group)):
                if group[j] in history_together[group[i]]:
                    return False
    return True


def generate_round_order(team_count: int) -> list[list[int]]:
    """
    生成一个随机的队伍出场顺序列表
    """
    if team_count <= 0:
        return []

    all_teams = list(range(1, team_count + 1))
    random.shuffle(all_teams)

    # 先按3队一组分组
    base_groups = []
    for i in range(0, team_count, 3):
        base_groups.append(all_teams[i:i + 3])

    result = []
    remaining_teams = []

    # 分离完整的3队组和剩余队伍
    for group in base_groups:
        if len(group) == 3:
            result.append(group)
        else:
            remaining_teams.extend(group)

    # 处理剩余队伍：分配到前面的3队组
    while remaining_teams:
        if result and len(result[-1]) == 3:
            result[-1].append(remaining_teams.pop(0))
        else:
            # 如果没有3队组了，创建4队组
            if len(remaining_teams) >= 4:
                result.append(remaining_teams[:4])
                remaining_teams = remaining_teams[4:]
            else:
                # 分配到前面的组
                for team in remaining_teams:
                    for group in result:
                        if len(group) < 4:
                            group.append(team)
                            break
                break

    return result


def generate_table(team_count: int):
    initial = generate_one_round_order(team_count)
    second = generate_new_round_order(team_count, [initial])
    final = generate_new_round_order(team_count, [initial, second])
    return {"first_round": initial, "second_round": second, "third_round": final}
